package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC42 {

    public int trap(int[] height) {
        int left = 0, right = height.length - 1, res = 0;
        while (left < right) {
            int curLowBound = Math.min(height[left], height[right]);
            if (curLowBound == height[left]) {
                ++left;
                while (left < right && height[left] < curLowBound) {
                    res += curLowBound - height[left++];
                }
            } else {
                --right;
                while (left < right && height[right] < curLowBound) {
                    res += curLowBound - height[right--];
                }
            }

        }

        return res;
    }


    public static void main(String[] args) {
        LC42 an = new LC42();
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        System.out.println(an.trap(arr));
    }
}
